package com.zsjt.basic.find;


/**
 * @author zhanb
 * @Date 2020/5/21
 */
public class InterpolationSearch {

    public static void main(String[] abc) {
        int [] array = new int [100];
        int i = 0;
        while(i<array.length){
            array[i] = i+1;
            i++;
        }
        System.out.println(search(array, 0, array.length - 1, 100));
    }
    /**
     *插值查找
     * @param array
     * @param left
     * @param right
     * @param findValue
     * @return
     */
    public static int search(int [] array , int left ,int right ,int findValue){
        //防止 findValue<array[0] || findValue>array[array.length-1]下标越界
        if(left> right || findValue<array[0] || findValue>array[array.length-1]) {
            return -1;
        }
        int mid = left+ ( right- left)* ( findValue - array[left]) / (array[right] - array[left]);
        int midValue =array[mid];
        if(findValue>midValue){
            //右递归
            return search(array,mid+1 ,right ,findValue);
        }else if(findValue<midValue){
            //左递归
            return search(array,left,mid-1,findValue);
        }else {
            return mid;
        }
    }
}
